1. Field of the Invention
The present invention relates to a technique for the scheduling of dynamically changing integrated circuit- and packet-switching traffic in a multibeam satellite-switched time-division multiple accessed (SS/TDMA) system. It is equally applicable to terrestrial communication systems, or more broadly to any type of centralized scheduling system involving arbitration of contention for resources among a plurality of users or equipments. More particularly, it pertains to an onboard satellite technique which repetitively and rapidly schedules both circuit and packet traffic employing a least-choice procedure to ensure efficient bandwidth and transponder utilization. The technique is based on requests for service from each zone to each zone, for a frame at a time, which is received from the ground via an order-wire facility.
2. Description of the Prior Art
The early satellite communication system designs employed an area coverage beam which provided interconnections on either a time-division multiple access (TDMA) basis or a frequency-division multiple access (FDMA) basis. Such designs had the disadvantage of low antenna gain and frequency reuse only by the use of polarization techniques. More recent designs use multiple narrow-angle fixed spot beams and scanning beams with onboard satellite switching, thereby permitting frequency reuse, lower satellite transmitter power, high antenna gain, and scheduling flexibility. Several systems using area, fixed spot, and scanning beams are possible. In one of these, a relatively small number of small fixed spot beams illuminate widely separated, relatively small footprints, to avoid co-channel interference, but thereby forego area coverage. In a second system, a large number of somewhat overlapping fixed spot beams cover an entire area, but with means taken to reduce co-channel interference. In a third and fourth system, area coverage is achieved by adding to a small number of small spot beams either an area coverage beam, or a scanning beam which accesses the entire area, in each case requiring means to mitigate co-channel interference. A fifth system uses a single scanning beam. A sixth system uses several scanning beams, which additionally may be limited-scan beams, which individually are constrained to one of several parallel strips.
An article "Analysis of a Switch Matrix for an SS/TDMA System" by Y. Ito et al in Proceedings of the IEEE, Vol. 65, No. 3, March 1977 at pp. 411-419 discloses a technique which, given a traffic demand matrix, constructs optimum switch assignments for a successive set of time slots constituting a frame, and which serves all of the traffic in the traffic demand matrix. This technique was not intended for onboard usage, but was intended to be used but once, in designing the satellite. For this purpose, the traffic demand matrix used is a statistical one, wherein an element (j,k) of the matrix gives the average traffic from zone j to zone k per unit time. Given a particular traffic demand matrix, the technique determines a switch schedule, consisting of the connections to be made from indicated zones to indicated zones, in each of a set of successive time slots, such that all the traffic in the traffic matrix is served. The assignment is optimal in the sense that the schedule comprises the fewest number of time slots. Having determined the frame schedule, it is intended that the schedule be fixed, and in actual operation that it be repeated and unchanging from frame to frame. Accordingly, the technique is not optimal in the sense of responding to actual changing demand on a frame-by-frame basis in a dynamic system. Also, this approach requires relatively complex logic which is undesirable for onboard implementation. In addition, it requires lengthy operation times, which are not expected to meet the stringent time requirement of dynamic frame-by-frame scheduling. A somewhat faster version of this technique is discussed by W. W. Wu in Proceedings, Fourth International Conference on Digital Satellite Communications, October 1978, at pp. 180-190.
Another scheduling technique is disclosed in U.S. Pat. No. 4,232,266 issued to A. Acampora on Nov. 4, 1980. It also is based on a statistical traffic matrix, and is intended for one-time computation in designing the system. As with the previous methods described above, it is relatively complex and lengthy to operate, thereby limiting its use in an onboard frame-to-frame dynamically scheduled system.
T. E. Stern discusses studies on a dynamic scheduling system in the report, "Packet Scheduling Protocols for Multiple Beam Communication Satellites", Department of Electrical Engineering and Computer Science, Columbia University. This system handles packets only, and assumes an order-wire facility for transmitting to the satellite requests for connections in single time slots. The requests are queued in a list, and are used in a first-come-first-served basis to determine the switch closure pattern for the next time slot. The schedule is then transmitted back to the earth by means of the order-wire facility. This procedure is not optimal in that it does not close the maximum number of switchpoints per slot, but it is fast enough for onboard use. However, this study does not address integrated cicuit- and packet-switching, and in addition, for large systems, the energy expended in the order-wire data transmission and onboard management of single requests becomes excessive.
The major advantages of integrating both circuit-switched and packet-switched traffic in a single system are to achieve economy by sharing transmission and switching equipment, and more efficient bandwidth and transponder utilization. Other advantages include economy of scale in transmission leases, improved survivability, more peak capacity for priority use, and flexibility of providing services which combine human and synthesized voice, graphics, and data.
A technique for combining circuit traffic and packet traffic has been disclosed in the article "A Combined Packet- and Circuit-Switched Processing Satellite System" by L. H. Ozarow in ICC Conference Record, June 10-14, 1979, Boston, Ma., Vol. 3 at pp. 24.5.1-25.5.5. For this system, the uplink bandwidth is divided into two parts. The major part is a TDMA uplink for circuit traffic. The remaining part is divided into a number of FDMA uplinks, which are randomly accessed by the packets. Non-colliding packets are queued onboard the satellite. The downlink consists of a single TDM channel. Onboard processing stuffs packets into downlink slots not used by circuits. However, the disclosed system is limited to a single downlink beam implementation since it assumes that each packet user can monitor the downlink to determine if a sent package has collided, and if so, to retransmit the packet.
The problem, therefore, remaining in the prior art is to provide a method of scheduling both circuit and packet traffic in a multibeam SS/TDMA environment with a superimposed frame structure, which provides efficient bandwidth and transponder utilization, and which operates within the time constraints of dynamic scheduling, and which has simple logic attractive for onboard implementation.